package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.List;

public class 分割等和子集 {

    public static void main(String[] args) {
        int[] a = {14, 9, 8, 4, 3, 2};
        int[] b = {1, 2, 5};
//        System.out.println(canPartition(a));
        System.out.println(canPartition(b));
    }

    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum % 2 == 1) {
            return false;
        }

        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (nums[i] == j) {
                    dp[i][j] = true;
                } else if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][target];
    }

}
